package leetcode_901_1000;

import common.SegmentTree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeeCode_996 {
    public static void main(String[] args) {
        System.out.println(numSquarefulPerms(new int[]{1, 17, 8}));
        System.out.println(numSquarefulPerms(new int[]{2,2,2}));
        System.out.println(numSquarefulPerms(new int[]{2,2,2,2,2,2,2,2,2,2,2,2}));
        System.out.println(numSquarefulPerms(new int[]{1,1,8,1,8}));
    }
    private static int numSquarefulPerms(int[] nums) {
        int n = nums.length;
        int[] vis = new int[n];
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = nums[i] + nums[j];
                int floor = (int)Math.floor(Math.sqrt(sum));
                if (floor * floor == sum){
                    grid[i][j] = 1;
                    grid[j][i] = 1;
                }
            }
        }
        List<Integer> tmp = new ArrayList<>();
        Set<Integer> used = new HashSet<>();
        Set<String> ans = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (used.contains(nums[i]))
                continue;
            used.add(nums[i]);
            dfs(grid, vis, i, tmp, nums, ans);
        }
        return ans.size();
    }
    private static void dfs(int[][] grid, int[] vis, int now, List<Integer> tmp, int[] nums, Set<String> ans){
        if (vis[now] == 1)
            return;
        vis[now] = 1;
        tmp.add(now);
        if (tmp.size() == vis.length){
            StringBuilder str = new StringBuilder();
            for (Integer i : tmp) {
                str.append(nums[i]);
                str.append(",");
            }
            ans.add(str.toString());
            vis[now] = 0;
            tmp.remove(tmp.size() - 1);
            return;
        }
        Set<Integer> used = new HashSet<>();
        for (int j = 0; j < grid[now].length; j++) {
            if (grid[now][j] == 1 && !tmp.contains(j)){
                if (used.contains(nums[j])){
                    continue;
                }
                used.add(nums[j]);
                dfs(grid, vis, j, tmp, nums, ans);
            }
        }
        vis[now] = 0;
        tmp.remove(tmp.size() - 1);
    }
}
